package one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二叉树的序列化与反序列化
 * 时间复杂度：O(n)
 * 思路：任选一种遍历方法存储二叉树（先序）
 */
public class Codec {

    private List<String> seq;
    private int curr;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        seq = new ArrayList<String>();
        preorder(root);
        return String.join(" ", seq);
    }
    private void preorder(TreeNode root){//先序遍历存储
        if(root == null){
            seq.add("null");
            return;//注意点，不要忘记
        }
        seq.add(Integer.toString(root.val));
        preorder(root.left);
        preorder(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        seq = Arrays.asList(data.split(" "));
        curr = 0;
        return calc();
    }
    private TreeNode calc(){
        if(seq.get(curr).equals("null")){
            curr++;
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt((seq.get(curr))));
        curr++;
        root.left = calc();
        root.right = calc();
        return root;
    }

}